import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


public class BinaryTreeProblems {

	private TreeNode root;
	private class TreeNode
	{
		TreeNode left;
		TreeNode right;
		int data;
	}
	
	public TreeNode add(int data)
	{
		TreeNode node = new TreeNode();
		node.left = null;
		node.right = null;
		node.data = data;
		
		// add new node to binary tree in level order therefore use Breath First Traversal
		if(root == null)
		{
			root = node;
		}
		else
		{
			Queue<TreeNode> queue = new LinkedList<TreeNode>();
			queue.add(root);
			while(!queue.isEmpty())
			{
				TreeNode current = queue.poll();
				if(current.left !=  null)
				{
					queue.add(current.left);
				}
				else
				{
					current.left = node;
					break;
				}
				if(current.right !=  null)
				{
					queue.add(current.right);
				}
				else
				{
					current.right = node;
					break;
				}
			}
		}
		return root;
	}
	
	public void breathFirstTraversal(TreeNode root)
	{
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		while(!queue.isEmpty())
		{
			TreeNode current = queue.poll();
			System.out.println(current.data);
			if(current.left !=  null)
			{
				queue.add(current.left);
			}
			if(current.right !=  null)
			{
				queue.add(current.right);
			}
		}
	}
	
	public int sumAllRootLeafs(TreeNode root)
	{
		return sumAllRootLeafs(root, 0);
	}
	
	private int sumAllRootLeafs(TreeNode root, int pathSum)
	{
		// Base condition
		if(root == null)
		{
			return 0;
		}

		pathSum = pathSum * 10  + root.data;

		// reached leaf node. calculate path sum
		if((root.left == null) && (root.right ==  null))
		{
			return pathSum;
		}
		else
		{
			return sumAllRootLeafs(root.left, pathSum) + sumAllRootLeafs(root.right, pathSum);
		}
	}
	
	private int printPath(List<Integer> list)
	{
		int pathSum =0;
		for(int i: list)
		{
			pathSum = pathSum *10 + i;
			System.out.print(i + " ");
		}
		System.out.println(pathSum);
		return pathSum;
	}
		
	public static void main(String[] args)
	{
		BinaryTreeProblems binaryTree = new BinaryTreeProblems();
		TreeNode root = binaryTree.add(1);
		binaryTree.add(2);
		binaryTree.add(3);
		binaryTree.add(4);
		binaryTree.add(5);
		binaryTree.add(6);
		
		binaryTree.breathFirstTraversal(root);
		int totalTreeSumRootLeafs = binaryTree.sumAllRootLeafs(root);
		System.out.println(totalTreeSumRootLeafs);
	}
}
